The rise in electronic and digital device technology has rapidly changed the way society communicates, interacts, and consumes goods and services. Modern computing devices allow organizations and users to have access to a variety of useful applications in many locations. Using such applications results in the generation of a large amount of data. Storing and retrieving the produced data is a significant challenge associated with providing useful applications and devices.
The data generated by online services and other applications can be stored at data storage facilities. As the amount of data grows, having a plurality of users sending and requesting data can result in complications that reduce efficiency and speed. Quick and reliable access in storage systems is important for good performance.
In a storage system, it is advantageous to group a plurality of small data objects into a large object. This is especially true in distributed storage systems where data objects are replicated across multiple storage devices. Storing a large data object in a distributed storage system is more efficient than storing a plurality of small data objects. In practice, the storage cost of small data objects is typically higher, because storing a plurality of these small data objects increases the number of Input/output Operations Per Second (“IOPS”) required for storing a specific amount of data. Encoding a plurality of such small data objects also results in a higher use of the available processing power, memory, bandwidth, metadata overhead, etc. Further, in practice small data objects typically consume more than the theoretical storage capacity, because of the effects of low-level padding, such as, for example, padding for alignment to the block size of a file system or block layer.
On the other hand, certain problems arise when a distributed storage system groups a plurality of small data objects, for example into a container object which can be more advantageously stored. Tracking the metadata concerning the smaller objects and container object conventionally results not only in overhead, but the potential for inconsistency and loss of data integrity. A conventional mechanism for providing metadata to allow for the mapping between the data objects and their respective container objects for subsequent retrieval is to schematically map the identifiers of the data objects to the identifiers of the respective container objects in a data structure such as an ordered Key Value Store (“KVS”). For example, suppose data objects A, B, C are grouped for storage by means of a container object C1, and data objects C, D, E are grouped for storage by means of a container object C2. A conventional data structure for lookup and retrieval of the objects could look like A->C1, B->C1, C->C1, D->C2, E->C2, F->C2.
In the context of a large-scale distributed object storage system, problems arise to keep such data structures efficient, responsive, robust and consistent. This is especially so when operations are performed which involve a large number of data objects, such as for example a repair operation of a broken or unavailable storage element, storage node, data center, etc. This is also the case during operations in which the contents of container objects is changed, for example during a compaction operation in which a subset of data objects stored in a plurality of container objects is merged into another container object in order to reclaim storage space of deleted or obsolete data objects.
It would be desirable to address at least these issues.